package cn.bellychang.leetcode.question021;

/**
 * @author ChangLiang
 * @date 2020/11/2
 */
public class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode newHead = null;
        ListNode newPrev = null;
        ListNode newCurr;

        ListNode list1Curr = l1;

        ListNode list2Curr = l2;

        // 循环不变量 newHead -> .. -> newCurr 连接好了
        // 类似归并排序的思路
        while (list1Curr != null || list2Curr != null) {


            if (list1Curr == null) {
                newCurr = list2Curr;
                list2Curr = list2Curr.next;
            }
            else if (list2Curr == null) {
                newCurr = list1Curr;
                list1Curr = list1Curr.next;
            } else if (list1Curr.val < list2Curr.val) {
                newCurr = list1Curr;
                list1Curr = list1Curr.next;
            } else {
                newCurr = list2Curr;
                list2Curr = list2Curr.next;
            }

            if (newHead == null) {
                newHead = newCurr;
            } else {
                newPrev.next = newCurr;
            }
            newPrev = newCurr;
        }
        return newHead;
    }
}
